package algorithm.greedy.basic.knapsack;

import java.util.*;

/**
 * 项目名称: god
 * 包 名 称: algorithm.greedy.basic.knapsack
 * 类 名 称: Backpack
 * 类 描 述: TODO
 * 创建时间: 2020/7/13 3:45 下午
 * 创 建 人: Justice
 * 每件物品的重量是w, 价值是v
 * n件物品总量不超过W的前提下，把那几件物品装入背包，可以使得背包的总价值量最大V
 */
public class Backpack {
    public static void select(String title, Comparator<Article> comparator) {
        Article[] articles = new Article[]{
                new Article(35, 10), new Article(30, 40),
                new Article(60, 30), new Article(50, 50),
                new Article(40, 35), new Article(10, 40),
                new Article(25, 30)
        };
        Arrays.sort(articles, comparator);
        // 背包容量W
        int capacity = 150;
        // 物品累计重量
        int weight = 0;
        // 物品累计价值
        int value = 0;
        List<Article> selectedArticles = new LinkedList<>();
        for (int i = 0; i < articles.length && weight < capacity; i++) {
            int newWeight = weight + articles[i].weight;
            if (newWeight <= capacity) {
                weight = newWeight;
                value += articles[i].value;
                selectedArticles.add(articles[i]);
            }
        }
        System.out.println("【" + title + "】");
        System.out.println("总价值：" + value);
        for (Article selectedArticle : selectedArticles) {
            System.out.println(selectedArticle);
        }
        System.out.println("-----------------------------");
    }
}
